% see: https://groups.google.com/forum/?fromgroups#!topic/comp.text.tex/s6z9Ult_zds
\makeatletter\let\ifGm@compatii\relax\makeatother 
\documentclass[10pt,t]{beamer}
\usefonttheme{professionalfonts}
\usefonttheme{serif}
\PassOptionsToPackage{pdfpagemode=FullScreen}{hyperref}
\PassOptionsToPackage{usenames,dvipsnames}{xcolor}
% \DeclareGraphicsRule{*}{mps}{*}{}
% \usepackage{../ibl}
\usepackage{../ibl}
\usepackage{present}
% \usepackage{xr}\externaldocument{../ibl} % read refs from .aux file
% \usepackage{catchfilebetweentags}
\usepackage{etoolbox} % from http://tex.stackexchange.com/questions/40699/input-only-part-of-a-file-using-catchfilebetweentags-package
\makeatletter
\patchcmd{\CatchFBT@Fin@l}{\endlinechar\m@ne}{}
  {}{\typeout{Unsuccessful patch!}}
\makeatother

\mode<presentation>
{
  \usetheme{boxes}
  \setbeamercovered{invisible}
  \setbeamertemplate{navigation symbols}{} 
}
\addheadbox{filler}{\ }  % create extra space at top of slide 
\hypersetup{colorlinks=true,linkcolor=blue} 

\title[Foundation of proofs] % (optional, use only with long paper titles)
{Foundation of proofs}

\author{{\small Jim Hef{}feron}}
\institute{
  \texttt{http://joshua.smcvt.edu/proofs}
}
\date{}


\subject{Foundation of proofs}
% This is only inserted into the PDF information catalog. Can be left
% out. 

\begin{document}
\begin{frame}
  \titlepage
\end{frame}



% ============================================================
\section{The need to prove}
\begin{frame}{In Mathematics we prove things}

`The base angles of an isoceles triangle are equal' seems obvious
to a person with mathematical aptitude.
\begin{center}\small
  \vcenteredhbox{\includegraphics{asy/pons.pdf}}
  \hspace*{2em}
  \vcenteredhbox{if $a\cong b$ then $\angle A\cong \angle B$}
\end{center}
Another example of a statement that seems obvious to such a person
is `each positive integer factors into a product of primes'. 

\pause
But is the Pythagorean Theorem `in a right triangle the 
square of the length of the hypoteneuse is equal to the sum
of the squares of the other two sides' perfectly clear?

A characteristic of our subject is 
that we show that new results follow logically from those already established.  
\end{frame}



\begin{frame}{Why we prove, not just convince}
% These assertions seem convincing 
% but turn out to be false.

\begin{itemize}
\pause\item
At first we may guess that the polynomial $n^2+n+41$ 
outputs only primes. 
\begin{center} \small\smallskip
  \begin{tabular}{r|rrrrrrrr}
    $n$        &$0$  &$1$  &$2$  &$3$  &$4$  &$5$  &$6$  &$7$ \\ \cline{2-9}
    $n^2+n+41$ &$41$ &$43$ &$47$ &$53$ &$61$ &$71$ &$83$ &$97$
  \end{tabular}\smallskip
\end{center}
\pause
However,  
for $n=41$ the output $41^2+41+41$ is divisible by~$41$.

\pause
\item 
When decomposed, $18=2^1\cdot 3^2$ has an odd number $1+2$ of 
prime factors, while
$24=2^3\cdot 3^1$ has an even number~$3+1$ of them.
We say that $18$ is of \textit{odd} type and
$24$ is of \textit{even} type.
\begin{center} \small\smallskip
  \makebox[0.9\textwidth]{
  \begin{tabular}{r|rrrrrrrrrr}
    $n$  &$1$   &$2$  &$3$  &$4$  &$5$  &$6$  &$7$ &$8$ &$9$ \\ \cline{2-10}
    type &even  &odd  &odd  &even &odd  &even &odd &odd &even
  \end{tabular}}\smallskip
\end{center}
P\`olya conjectured that if you fix an~$n>1$ and look at the numbers below it 
then the even types never outnumber the odd types. 
\pause
The first counterexample is $906\,150\,257$. 
\end{itemize}
\end{frame}
% >>> def prime_factors(n):
% ...     i = 2
% ...     factors = []
% ...     while i * i <= n:
% ...         if n % i:
% ...             i += 1
% ...         else:
% ...             n //= i
% ...             factors.append(i)
% ...     if n > 1:
% ...         factors.append(n)
% ...     return factors
% >>> for i in range(41):
% ...     print i, i*i+i+41, prime_factors(i*i+i+41)
% ... 
% 0 41 [41]
% 1 43 [43]
% 2 47 [47]
% 3 53 [53]
% 4 61 [61]
% 5 71 [71]
% 6 83 [83]
% 7 97 [97]
% 8 113 [113]
% 9 131 [131]
% 10 151 [151]
% 11 173 [173]
% 12 197 [197]
% 13 223 [223]
% 14 251 [251]
% 15 281 [281]
% 16 313 [313]
% 17 347 [347]
% 18 383 [383]
% 19 421 [421]
% 20 461 [461]
% 21 503 [503]
% 22 547 [547]
% 23 593 [593]
% 24 641 [641]
% 25 691 [691]
% 26 743 [743]
% 27 797 [797]
% 28 853 [853]
% 29 911 [911]
% 30 971 [971]
% 31 1033 [1033]
% 32 1097 [1097]
% 33 1163 [1163]
% 34 1231 [1231]
% 35 1301 [1301]
% 36 1373 [1373]
% 37 1447 [1447]
% 38 1523 [1523]
% 39 1601 [1601]
% 40 1681 [41, 41]


% ============================================================
\section{Elements of logic}

%..........
\begin{frame}
  \frametitle{Propositions}

A \alert{proposition} is an assertion that has a truth value, 
either `true' or `false'.

\pause
These are propositions: `$2+2=4$' 
and `Two circles in the plane intersect in either zero points, one point,
two points, or all of their points.'

\pause
These are not propositions: `$3+5$'
and `$x$ is not prime.'
\end{frame}



%..........
\begin{frame}[<+->]
  \frametitle{Negation}

Prefixing a proposition with \alert{not} inverts its truth value.

`It is not the case that $3+3=5$'
is true.

`It is not the case that $3+3=6$'
is false.

\pause
\bigskip
So the truth value
of `not~$P$' depends only on the truth of~$P$.
% Specifically, the truth value of \textit{not}~$P$ is 
% the opposite of the truth value of~$P$.  
We say `not' is a \alert{unary logical operator} or 
a \alert{unary boolean function} since it takes one input, a truth value, 
and yields as output a truth value.


\end{frame}


%..........
\begin{frame}
  \frametitle{Conjunction, disjunction}

A proposition consisting of the word \alert{and}
between two sub-propositions is true if
the two halves are true.

`$3+1=4$ and 
$3-1=2$'
is true

`$3+1=4$ and 
$3-1=1$'
is false

`$3+1=5$ and 
$3-1=2$'
is false

\pause
\bigskip
A compound proposition constructed with \alert{or}
between two sub-propositions is true if at least one half
is true.

`$2\cdot 2=4$ or 
$2\cdot 2\neq 4$'
is true

`$2\cdot 2=3$ or 
$2\cdot 2\neq 4$'
is false

`$2\cdot 2=4$ or 
$3+1=4$'
is true

\bigskip
\pause
So
`and' and `or'
are \alert{binary logical operators}.
\end{frame}





%..........
\begin{frame}
  \frametitle{Truth Tables}

Write $\neg P$ for `not~$P$', 
$P\wedge Q$ for `$P$~and~$Q$',
and $P\vee Q$ for `$P$~or~$Q$'.  
We can describe the action of these operators using \alert{truth tables}. 
\begin{center}
  \begin{tabular}[t]{c|c}
    $P$  &$\neg P$  \\ \hline
    $F$  &$T$  \\
    $T$  &$F$
  \end{tabular}
  \qquad
  \begin{tabular}[t]{cc|cc}
    $P$  &$Q$  &$P\wedge Q$  &$P\vee Q$  \\ \hline
    $F$  &$F$  &$F$          &$F$  \\
    $F$  &$T$  &$F$          &$T$  \\
    $T$  &$F$  &$F$          &$T$  \\
    $T$  &$T$  &$T$          &$T$  
  \end{tabular}
\end{center}

\pause
One advantage of this
notation is that it allows formulas of a complexity that would be awkward in
a natural language. 
For instance,
$(P\vee Q)\wedge \neg(P\wedge Q)$ is hard to express in 
English.
\end{frame}




%..........
\begin{frame}
Sometimes we prefer using $0$ for~$F$ and $1$ for~$T$.
One reason for the preference is that on 
the left side of the tables the rows make the ascending binary numbers.
\begin{center}
  \begin{tabular}[t]{c|c}
    $P$  &$\bar{P}$  \\ \hline
    $0$  &$1$  \\
    $1$  &$0$
  \end{tabular}
  \qquad
  \begin{tabular}[t]{cc|cc}
    $P$  &$Q$  &$P\cdot Q$  &$P+ Q$  \\ \hline
    $0$  &$0$  &$0$          &$0$  \\
    $0$  &$1$  &$0$          &$1$  \\
    $1$  &$0$  &$0$          &$1$  \\
    $1$  &$1$  &$1$          &$1$  
  \end{tabular}
\end{center}
In this context we symbolize `not~$P$' with $\bar{P}$,
we symbolize `$P$~and~$Q$' with $P\cdot Q$, and 
we symbolize `$P$~or~$Q$' with $P+Q$.

\pause
Note that $\bar{P}=1-P$.
The table makes clear why for `$P$~and~$Q$' we use a  
multiplication dot~$P\cdot Q$.
For `$P$~or~$Q$' the plus sign is a good symbol because 
`or' accumulates the truth value~$T$.
\end{frame}







%..........
\begin{frame}
  \frametitle{Other operators: Exclusive or}

Disjunction models
sentences meaning `and/or'.
In contrast,
`Live free or die', 
`Eat your dinner or no dessert', and
`Give me the money or the hostage gets it' all 
mean one or the other, but not both.
\begin{center}
  \begin{tabular}{cc|c}
    $P$  &$Q$  &$P$ \text{\small\textsc{XOR}} $Q$  \\ \hline
    $F$  &$F$  &$F$          \\
    $F$  &$T$  &$T$          \\
    $T$  &$F$  &$T$          \\
    $T$  &$T$  &$F$     
  \end{tabular}
\end{center}
\end{frame}




%..........
\begin{frame}
  \frametitle{Other operators: Implies}

We model `if $P$ then $Q$' this way.
\begin{center}
  \begin{tabular}{cc|c}
    $P$  &$Q$  &$P \rightarrow Q$  \\ \hline
    $F$  &$F$  &$T$          \\
    $F$  &$T$  &$T$          \\
    $T$  &$F$  &$F$          \\
    $T$  &$T$  &$T$     
  \end{tabular}
\end{center}
Here $P$ is the \emph{antecedent} while $Q$ is the 
\emph{consequent}. 

(There are some tricky aspects to this definition that we will discuss below.)
\end{frame}




%..........
\begin{frame}
  \frametitle{Other operators: Bi-implication}

Model `$P$ if and only if $Q$' with this.
\begin{center}
  \begin{tabular}{cc|c}
    $P$  &$Q$  &$P \leftrightarrow Q$  \\ \hline
    $F$  &$F$  &$T$          \\
    $F$  &$T$  &$F$          \\
    $T$  &$F$  &$F$          \\
    $T$  &$T$  &$T$     
  \end{tabular}
\end{center}
Mathematicians often write `iff'.
\end{frame}



%..........
\begin{frame}
  \frametitle{All binary operators}

This lists all of the binary logical operators.
\begin{center} \small
    \begin{tabular}{cc|c}
       $P$  &$Q$  &$P$ $\alpha_0$ $Q$  \\ \hline
       $F$  &$F$  &$F$          \\
       $F$  &$T$  &$F$          \\
       $T$  &$F$  &$F$          \\
       $T$  &$T$  &$F$     
     \end{tabular}
     \quad\begin{tabular}{cc|c}
       $P$  &$Q$  &$P$ $\alpha_1$ $Q$  \\ \hline
       $F$  &$F$  &$F$          \\
       $F$  &$T$  &$F$          \\
       $T$  &$F$  &$F$          \\
       $T$  &$T$  &$T$     
     \end{tabular}                
    \quad\ldots\quad                      
    \begin{tabular}{cc|c}
      $P$  &$Q$  &$P$ $\alpha_{15}$ $Q$  \\ \hline
      $F$  &$F$  &$T$          \\
      $F$  &$T$  &$T$          \\
      $T$  &$F$  &$T$          \\
      $T$  &$T$  &$T$ 
    \end{tabular}
\end{center}
\pause
\bigskip
These are the unary ones.
\begin{center} \small
  \begin{tabular}{cccc}
    \begin{tabular}{c|c}
       $P$  &$\beta_0 P$  \\ \hline
       $F$  &$F$          \\
       $T$  &$F$     
     \end{tabular}
    &\begin{tabular}{c|c}
       $P$  &$\beta_1 P$  \\ \hline
       $F$  &$F$          \\
       $T$  &$T$     
     \end{tabular}               
    &\begin{tabular}{c|c}
       $P$  &$\beta_2 P$  \\ \hline
       $F$  &$T$          \\
       $T$  &$F$     
     \end{tabular}
    &\begin{tabular}{c|c}
       $P$  &$\beta_3 P$  \\ \hline
       $F$  &$T$          \\
       $T$  &$T$     
     \end{tabular} 
  \end{tabular}
\end{center}
\pause
\bigskip
A zero-ary operator is constant so there are two:
$T$ and $F$.
\end{frame}




%..........
\begin{frame}
  \frametitle{Evaluating complex statements}
  No matter how intricate the propositional logic sentence, with patience 
  we can calculate how the output truth values
  depend on the inputs.
  Here is the work for
  $(P\rightarrow Q)\wedge (P\rightarrow R)$.
  \begin{center}
    \begin{tabular}{ccc|ccc}
      $P$  &$Q$  &$R$ &$P\rightarrow Q$ &$P\rightarrow R$ &$(P\rightarrow Q)\wedge (P\rightarrow R)$  \\ \hline
      $F$  &$F$  &$F$  &$T$  &$T$  &$T$   \\
      $F$  &$F$  &$T$  &$T$  &$T$  &$T$   \\
      $F$  &$T$  &$F$  &$T$  &$T$  &$T$   \\
      $F$  &$T$  &$T$  &$T$  &$T$  &$T$   \\[0.75ex]
      $T$  &$F$  &$F$  &$F$  &$F$  &$F$   \\
      $T$  &$F$  &$T$  &$F$  &$T$  &$F$   \\
      $T$  &$T$  &$F$  &$T$  &$F$  &$F$   \\
      $T$  &$T$  &$T$  &$T$  &$T$  &$T$      
    \end{tabular}
  \end{center}
  We've just decomposed the statement into its 
  components $P\rightarrow Q$, etc., and built up to the full sentence.
\end{frame}




%..........
\begin{frame}
  \frametitle{Tautology, Satisfiability, Equivalence}
  A formula is a \emph{tautology} if it evaluates to $T$ for every value
  of the variables.
  A formula is \emph{satisfiable} if it evaluates to $T$ for at least one
  value of the variables.

  \pause
  Two propositional expressions are \alert{logically equivalent} if they
  give the same input-output relationship. 
  We can check that expressions 
  $E_0$ and~$E_1$ are equivalent by using truth tables to
  verify that  
  $E_0\leftrightarrow E_1$ is a tautology.  

  For instance, $P\wedge Q$ and $Q\wedge P$ are equivalent.
  Another example is that $P\rightarrow Q$ and $\neg Q\rightarrow \neg P$ 
  are equivalent.
\end{frame}






% %..........
% \begin{frame}
%   \frametitle{Topic: Sheffer stroke}
% This single operator
% \begin{center}
%   \begin{tabular}{cc|c}
%     $P$  &$Q$  &$P \mathbin{\text{{\small\textsc{nand}}}} Q$  \\ \hline
%     $F$  &$F$  &$T$          \\
%     $F$  &$T$  &$T$          \\
%     $T$  &$F$  &$T$          \\
%     $T$  &$T$  &$F$     
%   \end{tabular}
% \end{center}
% can be used to produce any truth table.
% For instance, $P\mathbin{\text{\small\textsc{nand}}}P$ is equivalent to $\neg P$.
% \pause
% The \textsc{nor} operation is also complete.
% \end{frame}




% %..........
% \begin{frame}
%   \frametitle{Topic: McCarthy Or}
% The \texttt{or} operator used in computer languages is somewhat
% like the one discussed here but it is \emph{short-circuited}.
% In this expression
% \begin{center}
%   \texttt{if isEven(x) or isPrime(x)}
% \end{center}
% if \texttt{x} is even then \texttt{isPrime(x)} will not be evaluated.
% \end{frame}




%..........
\begin{frame}
  \frametitle{Non-obvious lines in the implication table}
\begin{center}
  \begin{tabular}{cc|c}
    $P$  &$Q$  &$P \rightarrow Q$  \\ \hline
    $F$  &$F$  &$T$          \\
    $F$  &$T$  &$T$          \\
    $T$  &$F$  &$F$          \\
    $T$  &$T$  &$T$     
  \end{tabular}
\end{center}
Our definition of implies takes
`if Babe Ruth was president then $1+2=4$'
to be a true statement, 
because its antecedent is false.
Similarly we take
`if Mallory reached the summit of Everest then $1+2=3$' 
to be true because its consequent is true.
Why define it this way?

\pause
Standard mathematical practice defines implication so that
\begin{center}
  if $n$ is a perfect square then $n$ is not prime
\end{center}
is true for all $n\in\N$.
\pause  Then $n=6$ shows that we need $F\rightarrow T$ to evaluate to $T$.  
\pause Use $n=3$ to get that $F\rightarrow F$ yields $T$.
\pause For $T\rightarrow T$ take $n=4$.
\end{frame}
% http://www.earlham.edu/~peters/courses/log/mat-imp.htm
\begin{frame}\vspace*{-1ex}
\frametitle{Points about implication}
\begin{center}
  \begin{tabular}{cc|c}
    $P$  &$Q$  &$P \rightarrow Q$  \\ \hline
    $F$  &$F$  &$T$          \\
    $F$  &$T$  &$T$          \\
    $T$  &$F$  &$F$          \\
    $T$  &$T$  &$T$     
  \end{tabular}
\end{center}
\begin{itemize}
\item As noted on the prior slide, 
  the antecedent~$P$ need not be materially connected to the 
  consequent~$Q$.
\pause
\item Also noted there are:
  (1)~if the antecedent~$P$ is false then the statement as a whole is true, 
  said to be \alert{vacuously true}
  and (2)~if the consequent~$Q$ is true then the statement as a whole is true.
% \pause 
% \item If the antecedent~$P$ is true then the statement as a whole has the
%   same truth value as the consequent.
\pause
\item Truth tables show that $P\rightarrow Q$
  is logically equivalent to $\neg(P\wedge \neg Q)$, 
  to $\neg P\vee Q$,
  and also to the \alert{contrapositive}~$\neg Q\rightarrow \neg P$.
\pause
\item 
  On a table in front of you are four cards, 
  marked `A', `B', `0', and~`1'.
  You must verify the truth of the implication, 
  `if a card has a vowel on the one side 
  then it has an even number on the other.'  
  How to do it, turning over the fewest cards?
  (This is the \textit{Wason test}; fewer than $10\%$ of Americans 
  get it right.)
% \item In ``Fred is Mike's brother's son and therefore Fred is Mike's nephew'' 
%   the statement ``Fred is Mike's nephew'' is a \textit{material consequence} 
%   of ``Fred is Mike's brother's son'' but not a formal consequence. 
%   This is because the validity of the argument depends on the 
%   internal content of 
%   the premise and conclusion, including the meanings of `brother', `son', 
%   and `nephew', rather than on the logical form of the argument.
\end{itemize}
\end{frame}
% See http://www.cs.cornell.edu/Info/People/gries/symposium/clarke.htm


\begin{frame}
\frametitle{Predicates, Quantifiers}
The statement
\begin{equation*}
  \text{`if $n$ is odd then $n$ is a perfect square'}
  \tag{$*$}
\end{equation*}
involves two clauses, `$n$ is odd' and `$n$ is square'.
For each the truth value depend on the variable.
A \alert{predicate} is a truth-valued function.
An example is the function~$\text{Odd}$ that takes an integer as input and 
yields either $T$ or~$F$, as in~$\text{Odd}(5)=T$.
Another example is $\text{Square}$, as in $\text{Square}(5)=F$.

\pause
A mathematician stating~($*$) would mean that
it holds for all~$n$.
We denote `for all' by $\forall$ so the statement is formally written
$\forall n\in\N \big[\text{Odd}(n)\rightarrow\text{Square}(n)\big]$.
(It is of course a false statement.)

\pause
A
\alert{quantifier} describes for how many values of the
variable the clause must be true, in order for the statement as a whole to
be true.
Besides `for all' 
the other common quantifier is 
`there exists', denoted $\exists$.
The statement
$\exists n\in\N \big[\text{Odd}(n)\rightarrow\text{Square}(n)\big]$
is true.
\end{frame}
\begin{frame}
Examples of statements written formally, with explicit quantifiers.

\begin{itemize}
\item Every number is divisible by $1$.
  \begin{equation*}
    \forall n\in\N\,\big[1\divides n\big]
  \end{equation*}

\pause
\item There are five different powers~$n$ where the equation $2^n-7=a^2$ has a solution.
  \begin{multline*}
    \exists n_0, \ldots, n_4\in\N\, \big[(n_0\neq n_1) 
                                     \wedge (n_0\neq n_2) 
                                     \wedge \cdots 
                                     \wedge (n_3\neq n_4)  \\
                                     \wedge \exists a_0\in\N(2^{n_0}-7=a_0^2)
                                     \wedge\cdots\wedge
                                     \exists a_4\in\N(2^{n_4}-7=a_4^2)\big]
  \end{multline*}

\pause
\item Any two integers have a common multiple.
  \begin{equation*}
    \forall n_0,n_1\in\N\;\exists m\in\N\,
        \big[(n_0\divides m)\wedge (n_1\divides m)\big]
  \end{equation*}

\pause
\item The function~$\map{f}{\R}{\R}$ is continuous at $a\in\R$.
  \begin{equation*}
    \forall \varepsilon >0\;\exists \delta > 0\;\forall x\in\R\,
        \big[(\absval{x-a}<\delta)\rightarrow (\absval{f(x)-f(a)}<\varepsilon)\big]
  \end{equation*}
\end{itemize}
\end{frame}
\begin{frame}
The negation of a `$\forall$' statement is a `$\exists\,\neg$' 
statement.
For instance, the negation of `every raven is black' is 
`there is a raven that is not black'.

\pause
A mathematical example is that 
the negation of `every odd number is a perfect square'
\begin{equation*}
  \forall n\in\N\,\big[ \text{Odd}(n)\rightarrow\text{Square}(n)\big]
\end{equation*}
is 
\begin{equation*}
  \exists n\in\N\,\neg\big[ \text{Odd}(n)\rightarrow\text{Square}(n)\big]
\end{equation*}
which is equivalent to this.
\begin{equation*}
  \exists n\in\N\,\big[\text{Odd}(n)\wedge\neg\text{Square}(n)\big]
\end{equation*}
Thus a person could show that `every odd number is a perfect square' is false
by finding a number that is both odd and not a square.

\pause
Simililarly the negation of a `$\exists$' statement is a~`$\forall\,\neg$'
statement. 
\end{frame}






%..........
% \begin{frame}
% \ex
% \end{frame}


%...........................
% \begin{frame}
% \ExecuteMetaData[../gr3.tex]{GaussJordanReduction}
% \df[def:RedEchForm]
% 
% \end{frame}
\end{document}
